import java.util.*;


public class BinaryTreeExample {


	public static BinaryTreeNode buildTree() {
		
		return 	new BinaryTreeNode( "A",
					new BinaryTreeNode( "B", null, null ),
					new BinaryTreeNode( "C",
						new BinaryTreeNode("D",
							new BinaryTreeNode("F", null, null ),
							null ),
						new BinaryTreeNode( "E",
							null,
							new BinaryTreeNode( "G", null, null )
						)
					)
				);

	}


	public static int height( BinaryTreeNode tree ) {
        
		int leftChildHeight = -1;
		if (tree.left != null) {
			leftChildHeight = height( tree.left ); 
		}

		int rightChildHeight = -1;
		if (tree.right != null) {
			rightChildHeight = height( tree.right );
		}

		return Math.max(leftChildHeight, rightChildHeight) + 1;
	}


	public static int size( BinaryTreeNode tree ) {
		
		int leftSize = 0;
		if ( tree.left != null ) {
			leftSize = size( tree.left );
		}

		int rightSize = 0;
		if ( tree.right != null ) {
			rightSize = size( tree.right );
		}

		return leftSize + rightSize + 1;
	}


	public static BinaryTreeNode duplicate( BinaryTreeNode tree ) {
		
		if (tree == null) {
			return null;
		}
		else {
			return new BinaryTreeNode( tree.element,
										duplicate( tree.left ),
										duplicate( tree.right ));
		}
	}

	
	private static void processNode( BinaryTreeNode tree ) {

		System.out.print(tree.element + " ");
	}

	
    public static void preOrderTraversal(BinaryTreeNode tree) {

		processNode(tree);

		if (tree.left != null) {
			preOrderTraversal(tree.left);
		}

		if (tree.right != null) {
			preOrderTraversal(tree.right);
		}
    }


    public static void postOrderTraversal(BinaryTreeNode tree) {

		if (tree.left != null) {
			postOrderTraversal(tree.left);
		}

		if (tree.right != null) {
			postOrderTraversal(tree.right);
		}

		processNode(tree);
    }


    public static void inOrderTraversal(BinaryTreeNode tree) {

		if (tree.left != null) {
			inOrderTraversal(tree.left);
		}

		processNode(tree);

		if (tree.right != null) {
			inOrderTraversal(tree.right);
		}
    }

	
    public static void levelOrderTraversal(BinaryTreeNode tree) {

		Queue q = new LinkedList();

		q.offer(tree);

		while (!q.isEmpty()) {
		
			BinaryTreeNode n = (BinaryTreeNode)q.poll();

			processNode(n);

			if (n.left != null) {
				q.offer( n.left );
			}

			if (n.right != null) {
				q.offer( n.right );
			}
		}

    }

	
	public static void iterativePreOrderTraversal(BinaryTreeNode tree) {

		Stack stack = new Stack();

		stack.push(tree);

		while (!stack.isEmpty()) {
		
			BinaryTreeNode n = (BinaryTreeNode)stack.pop();

			processNode(n);

			if (n.right != null) {
				stack.push( n.right );
			}

			if (n.left != null) {
				stack.push( n.left );
			}
		}
	}


	public static void main(String[] args) {

		BinaryTreeNode tree = buildTree();

		tree = duplicate( tree );
		
		System.out.println( "height = " + height(tree) );
		System.out.println("");
		
		System.out.println( "size = " + size(tree) );
		System.out.println("");
		
		System.out.print( "Pre-Order: ");
		preOrderTraversal( tree );
		System.out.println("\n");
		
		System.out.print( "Post-Order: ");
		postOrderTraversal( tree );
		System.out.println("\n");
		
		System.out.print( "In-Order: ");
		inOrderTraversal( tree );
		System.out.println("\n");
		
		System.out.print( "Level-Order: ");
		levelOrderTraversal( tree );
		System.out.println("\n");
		
		System.out.print( "Iterative Pre-Order: ");
		iterativePreOrderTraversal( tree );
		System.out.println("\n");
	}


}